package medium;
/*
200. 岛屿数量
解题思路：dfs
 */
public class LeeCode200 {

  public static void main(String[] args) {
    System.out.println(new LeeCode200().numIslands(new char[][]{
            {'1','1','1'},
            {'0','1','0'},
            {'1','0','0'},
            {'1','0','1'}
    }));
  }

  public int numIslands(char[][] grid){
    if (grid == null ||grid.length == 0){
      return 0;
    }
    int row = grid.length;
    int col = grid[0].length;
    int res = 0;
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        if (grid[i][j] == '1'){
          res++;
          dfs(grid,i,j);
        }
      }
    }
    return res;
  }

  public void dfs(char[][] grid, int row, int col) {
    int nr = grid.length;
    int nc = grid[0].length;

    if (row < 0 || col < 0 || row >= nr || col >= nc || grid[row][col] == '0') {
      return;
    }

    grid[row][col] = '0';
    dfs(grid, row - 1, col);
    dfs(grid, row + 1, col);
    dfs(grid, row, col - 1);
    dfs(grid, row, col + 1);
  }

}
